package fibonacci;

/**
 * Created with IntelliJ IDEA.
 * Description:斐波那契数列 -- 三步问题
 * User: YJ
 * Date: 2023-9-20
 * Time: 21:10
 */
public class Fibonacci1 {
    public static int fibonacci(int n) {
        // 1.创建dp表
        // 2.初始化
        // 3.填表
        // 4.返回值
        //处理边界
        int MOD = (int) (1e9 + 7);
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= n; i++) {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(3));
    }
}
